package org.example.code.test2024.ten_mouth;

import java.util.*;


public class test1016 {

    public long kthLargestLevelSum(TreeNode root, int k) {
        if (root == null) {
            return -1;
        }
        List<Long> list = new ArrayList<>();
        fun(list, root, 0);
        list.sort(Comparator.reverseOrder());
        if (list.size() < k) {
            return -1;
        }
        return list.get(k - 1);
    }

    private void fun(List<Long> list, TreeNode node, int k) {
        if (node == null) {
            return;
        }
        if (k >= list.size()) {
            list.add((long) node.val);
        } else {
            list.set(k, list.get(k) + node.val);
        }
        fun(list, node.left, k + 1);
        fun(list, node.right, k + 1);
    }

    public long maximumOr(int[] nums, int k) {
        if(nums.length==0){
            return 0;
        }
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        left[0]=nums[0];
        for(int i=1;i< nums.length;i++){
            left[i]=left[i-1]|nums[i];
        }
        right[nums.length - 1] = nums[nums.length - 1];
        for (int i = nums.length- 2; i >= 0; i--) {
            right[i] = right[i + 1] | nums[i];
        }
        long max = 0;
        for (int i=0;i< nums.length;i++) {
            long t = nums[i] * (1L << k);
            long l = i > 0 ? left[i - 1] : 0;
            long r = i < nums.length - 1 ? right[i + 1] : 0;
            long cur = l|t|r;
            max = Math.max(max, cur);
        }
        return max;
    }

    public int countBeautifulPairs(int[] nums) {
        int sum = 0,n = nums.length;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int a = nums[i];
                while(a>10){
                    a=a/10;
                }
                int b = nums[j]%10;
                if(gcd(a,b)){
                    sum++;
                }
            }
        }
        return sum;
    }

    private boolean gcd(int x,int y){
        for(int i=2;i<=Math.min(x,y);i++){
            if(x%i==0&&y%i==0){
                return false;
            }
        }
        return true;
    }

    public String removeTrailingZeros(String num) {
        int n = num.length();
        StringBuilder sb = new StringBuilder(num);
        for(int i=n-1;i>=0;i--){
            if(num.charAt(i)=='0'){
                sb.deleteCharAt(i);
            }else{
                break;
            }
        }
        return sb.toString();
    }

}
